// 插入排序

/**
 * 算法描述：
 *  1. 把待排序的数组分为已排序和未排序两部分，初始的时候默认第一个元素认为是已经排好序的
 *  2. 从第二个元素开始，在已经排好序的子数组中寻找到该元素合适的位置并插入该位置
 *  3. 重复上述过程，直到最后一个元素被插入有序子数组
 * 
 * 
 * 复杂度：
 *  时间复杂度： O(n^2)
 *  空间复杂度： O(1)
 * **/ 

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let value = arr[i];
        let position = i;

        while (position > 0 && arr[position - 1] > value) {
            arr[position] = arr[position - 1];
            position --;
        };
        arr[position] = value;
    };

    return arr;
};


const arr = [1, 7, 4, 3, 2, 6];

console.log(insertSort(arr));